// #include <iostream>
// using namespace std;
//
// #define DAY 7
// int main()
// {
//     system("pause");
//     cout<<"hello"<<endl;
//     cout<<"一周有"<<DAY<<"天"<<endl;
//     cout<<"short:"<<sizeof(short)<<endl;
//     cout<<"int:"<<sizeof(int)<<endl;
//     cout<<"long:"<<sizeof(long)<<endl;
//     float a=3.1415926535;
//     cout<<"float:"<<a<<endl;//在代码中如果没有.f来要求位数一般都保留五位小数
//
//
// return 0;
// }
//short:-32768~32767(超出的话相当于重新从-32768开始计算
//int long   long long
//常用的\t占八个空格，水平制表 endl 作用等于\n

//C风格字符串：char str(名字） [] = "  ";
//C++风格：string(等同于char) str(名字) = "  ";    用前要包含头文件<string>

//bool类型
// #include <iostream>
// using namespace std;
//
// int main()
// {
//     system("pause");
//     bool flag = true;
//     cout<<flag<<endl;
//     flag = false;
//     cout<<flag<<endl;
//
//  return 0;
// }



//数据的输入与输出(cin与>>)
//包括整型输入 浮点型输入 字符型输入(char类型->ASCII码值)  字符串型输入(string)   布尔类型输入

// #include <iostream>
// using namespace std;
//
// int main()
// {
//     int a=0;
//     cout<<"please enter an integer:";
//     cin>>a;
//     cout<<"your integer is:"<<a<<endl;
//
//
//     return 0;
// }


//结构顺序
//if-else(包括单行 多行 多条件)
//多行
// #include <iostream>
// using namespace std;
//
// int main() {
//     int a=0;
//     cout<<"please enter your score: "<<endl;
//     cin>>a;
//     cout<<"your score is:"<<a<<endl;
//     if (a >= 600) {
//         cout<<"Congratrulation!your score has passed the exam"<<endl;
//     }
//     else {
//         cout<<"That is a pity!"<<endl;
//     }
//     return 0;
// }

// //if-else之三只小猪称体重
// #include <iostream>
// using namespace std;
//
// int main() {
//     //输入三只小猪体重
//     int a,b,c;
//     cout<<"please input three pigs weight(kg/one):"<<endl;
//     cout<<"first one:";cin>>a;
//     cout<<"second one:";cin>>b;
//     cout<<"third one:";cin>>c;
//     //判断   有更简单的方法
//      if (a>b) {
//          if (b>c){
//              cout<<"the rank is:"<<"one two three"<<endl;
//          }
//          else if (c>b){//c>b,c再和a比较
//              if (a>c) {
//                  cout<<"the rank is:"<<"one three two"<<endl;
//              }
//              else if (a<c){
//                  cout<<"the rank is:"<<"three one two"<<endl;
//              }
//              else {//a=c
//                  cout<<"the rank is:"<<"one = three > two"<<endl;
//              }
//          }
//          else if (b=c) {
//              cout<<"the rank is:"<<"one > two =three"<<endl;
//          }
//      }
//     else if (a<b) {//a<b
//         if (a>c) {
//             cout<<"the rank is:"<<"two one three"<<endl;
//         }
//         else if (a<c){
//             if (b>c) {
//                 cout<<"the rank is:"<<"two three one"<<endl;
//             }
//             else if (c>b){
//                 cout<<"the rank is:"<<"three two one"<<endl;
//             }
//             else if(b=c){
//                 cout<<"the rank is:"<<"two = three > one"<<endl;
//             }
//         }
//         else if (a=c) {
//             cout<<"the rank is:"<<"two > one = three"<<endl;
//         }
//     }
//     else if(a=b) {
//         if (a>c) {
//             cout<<"the rank is:"<<"one = two > three"<<endl;
//         }
//         else if (a<c){
//             cout<<"the rank is:"<<"three > one = two"<<endl;
//         }
//         else if (a=b) {
//             cout<<"the rank is:"<<"one = two = three"<<endl;
//         }
//     }
//
//     return 0;
// }

//三目运算(在C++中返回的是变量可以继续赋值)
// #include <iostream>
// using namespace std;
//
// int main() {
//     int a=10, b=20;
//     int c=(a>b?a:b);
//     cout<<c<<endl;
//     int d=100;
//     (d>c?d:c)=1000;
//     cout<<"d = "<<d<<endl;
//     cout<<"c = "<<c<<endl;
//     return 0;
// }

//for循环之敲桌子游戏
/*
 规则：只要出现7，就输出敲桌子！
 特殊数字：1.7的倍数    2.包含7(个位 十位 百位)
 */
// #include<iostream>
// using namespace std;
//
// int main() {
//     int i =1;
//     int ge,shi,bai;
//     int count = 0;
//     for (i;i <= 100;i++) {
//         ge = i % 10;
//         shi = (i/10)%10;
//         bai = i/100;
//         if (i % 7 ==0 || ge == 7 || shi == 7 || bai == 7) {
//             cout<<"Boom!!"<<endl;
//             count++;
//         }
//         else {
//             cout<<i<<endl;
//         }
//     }
//     cout<<"The num '7' has emerged count "<<count<<" !"<<endl;
//     return 0;
// }

//嵌套for循环打印图形
// #include<iostream>
// using namespace std;
//
// int main() {        //外层执行一次，内层执行一周(打印的终极原理)
//     for (int i = 0; i < 10; i++) {
//         for (int j = 0; j < 10; j++) {
//             cout<<"* ";
//         }
//         cout << endl;
//     }
//     return 0;
// }

//break退出for循环
// #include<iostream>
// using namespace std;
//
// int main(void) {
//     for (int i = 1; i <= 10; i++) {
//         cout << i << endl;
//         if (i == 6) {
//             break;
//         }
//     }
//     return 0;
// }

//break在嵌套循环里
// #include<iostream>
// using namespace std;
//
// int main() {        //外层执行一次，内层执行一周(打印的终极原理)
//     for (int i = 0; i < 10; i++) {
//         for (int j = 0; j < 10; j++) {
//              if (j == 4) {
//                  break;
//             }
//             cout<<"* ";
//         }
//         cout << endl;
//     }
//     return 0;
// }

//continue在循环中用法
// #include<iostream>
// using namespace std;
//
// int main() {
//     for (int i = 0;i <= 100;i++) {
//         if (i % 2 != 0) {
//             continue;//可以用来筛选条件，像这里就只会输出偶数;执行到这一行不往下执行而是重新来
//         }
//         cout << i << endl;
//     }
//     return 0;
// }

//switch语句
// #include <iostream>
// using namespace std;
//
// int main() {
//     int score = 0;
//     cout<<"please enter a score for the movie:";
//     cin>>score;
//     switch (score) {
//         case 10:
//             cout<<"Very Good!";
//             break;                  //如果没有break的话switch中的语句会一直执行下去
//         case 9:
//             cout<<"Good!";
//             break;
//         case 8:
//             cout<<"Common!";
//             break;
//         default:                    //default语句是除了case中的数字，其他输入的都会输出default中的值
//             cout<<"Your sight is really high!";
//     }
//     return 0;
// }
/*if和switch区别
1.switch结构清晰，框架易懂;if逻辑语法可延伸拓展(例如嵌套 多行)，但较为复杂
2.switch的执行效率更高
*/

//while语句
// #include <iostream>
// using namespace std;
//
// int main() {
//     int i=0;
//     while (i<10) {
//         cout<<i<<endl;
//         i++;
//     }
//     return 0;
// }

// #include <iostream>
// #include<cstdlib>
// #include<ctime>
// using namespace std;
//
// int main() {
//     int rad_num = rand() % 100 + 1; // 0 + 1 ~ 99 + 1
//
//     //cout << rad_num << endl;
//     int val;
//     cout<<"please enter a  int number for guess: ";
//     while (1) { //（1）表示循环会直接执行，不需要条件，如果没有break程序会一直执行
//         cin >> val;
//         if (val > rad_num) {
//             cout<<"Too Big"<<endl;
//         }
//         else if (val < rad_num) {
//             cout<<"Small"<<endl;
//         }
//         else {
//             cout<<"Congratrulation! Game over."<<endl;
//             break;
//         }
//     }
//     return 0;
// }


// #include<iostream>
// #include<cstdlib>
// #include<ctime>
// using namespace std;
//
// int main() {
//     srand((unsigned int)time(NULL));        //获取当前时间作为种子序列
//     int number = rand() % 100 +1;           //生成随机数
//     int num;
//     cout<<"Please input a int num :"<<endl;
//     while (1) {
//         cin>>num;
//         if (num > number) {
//             cout<<"Too Big"<<endl;
//         }
//         else if (num < number) {
//             cout<<"Too Small"<<endl;
//         }
//         else {
//             cout<<"Congratrulation! Game over."<<endl;
//             break;
//         }
//     }
//     return 0;
// }

//do-while循环结构
// #include<iostream>
// using namespace std;
//
// int main() {
//     int nums=1;
//
//     do {
//         cout<<nums<<endl;       //会先执行一遍，不论while中的条件是什么
//         //nums ++;
//     }
//     while (nums < 1);
//     return 0;
// }


//水仙花问题
/*
1.输出所有三位数
2.找到水仙花数
3.判断是否是水仙花数
    个位*3 + 十位*3 +百位*3 ？=本身
*/
// #include<iostream>
// using namespace std;
//
// int main() {
//     int i =100;
//     int ge,shi,bai;
//     int sum;
//     do{
//         ge = i % 10;
//         shi = (i/10)%10;
//         bai = i/100;
//         sum = ge*ge*ge + shi*shi*shi + bai*bai*bai;
//         if (sum == i) {
//             cout<<i<<endl;
//         }
//         i++;
//     }while (i < 1000);
//     return 0;
// }

//打印乘法口诀表
// #include <iostream>
// using namespace std;
//
// int main() {
//     int i,j;
//     for (i = 1;i <= 9;i++) {
//         for (j = 1;j <= i;j++) {
//             cout<<j<<"*"<<i<<"="<<j*i<<"  ";
//         }
//         cout<<endl;
//     }
//     return 0;
// }

//数组


//一维数组
//定义方式
/*1.数据类型 数组名[数组长度]
2.数据类型 数组名[数组长度]={值1，值2.....}
3.数据类型 数组名[]={值1，值2.....}
*/
/*一维数组可以用来统计整个数组在内存中的长度    sizeof(arr) or sizeof(arr[])
 *可以通过数组名查看数组首地址
 */
 // #include <iostream>
 // using namespace std;

 // int main() {
 //    1.数据类型 数组名[数组长度]
 //     int arr1[5];
 //     arr1[0] = 10;
 //     arr1[1] = 20;
 //     arr1[2] = 30;
 //    复制方式
 //    2.数据类型 数组名[数组长度]={值1，值2.....}
 //    数组初始化的没有填写每个下标的值，那么默认为0
 //     int arr[5]={0,1,2,4,5};
 //     for(int i=0;i<5;i++) {
 //         cout<<arr[i]<<" "<<endl;
 //     }
 //    3.数据类型 数组名[]={值1，值2.....}
 //    int arr2[]={1,2,3,4,5};
 //    未标明长度，数组会自己推测
 //     return 0;
 // }

// #include <iostream>
// using namespace std;
// int main() {
//     int arr[4]={1,2,3,0};
//     int max=0;       //初始化最大值为0
//     for (int i=0;i<4;i++) {  //遍历数组中元素
//         if (arr[i] > max) {
//             max = arr[i];    //随时更新
//         }
//     }
//     cout<<max<<endl;
//
//     return 0;
// }

// #include<stdio.h>//S=1+(1+2)+(1+2+3).....+(1+2+...+n)
// int main() {
//     int n,i=1,sum=0,res=0;
//     scanf("%d",&n);
//     while (i <= n) {
//         sum+=i;
//         res=res + sum;    //更新 输入2 -> res=1 + sum=(1+2)
//         i++;
//     }
//     printf("%d\n",res);
//     return 0;
// }
//由这两个例子，引出迭代、排序中一个重要思想——数据更新，有了更新，就可以完成许多算法问题，例如排序，找最大值等等


//数组之元素逆置

//现在还是不理解[]与数组名，i之间的关系
// #include<iostream>
// using namespace std;
//
// int main() {
//     int arr[5]={1,3,2,5,4};
//     int start = 0;
//     int end = sizeof(arr)/sizeof(arr[0]) - 1;//sizeof在这里是衡量数组长度的工具，计算完后是一个整数
//     while (start <= end) {
//         int temp;
//         temp = arr[start];  //这里的start=0，相当于temp=arr[0]
//         arr[start] = arr[end];
//         arr[end] = temp;
//         start++;
//         end--;
//     }
//     for (int i = 0; i<5; i++) {
//         cout << arr[i] << endl;
//     }
//     return 0;
// }

//数组之冒泡排序   两层for循环 -> 交换数字
// #include<iostream>
// using namespace std;
//
// int main() {
//     int arr[9]={1,4,2,5,67,8,9,34,7};
//     for(int i=0;i<9;i++)
//         cout<<arr[i]<<" ";//排序前
//     //开始排序
//     //总排序轮数（外层for循环）为 元素个数 - 1
//     for (int i = 0;i < 9-1;i++) {
//         //每轮对比次数（内层for循环）为 元素个数 - 当前轮数 - 1
//         for (int j = 0;j < 9 - i -1;j++) {
//             //数字交换
//             if (arr[j] > arr[j + 1]) {
//                 int temp = arr[j];
//                 arr[j] = arr[j + 1];
//                 arr[j + 1] = temp;
//             }
//         }
//     }
//     cout<<endl;
//     for(int i=0;i<9;i++)//排序后
//         cout<<arr[i]<<" ";
//     return 0;
// }


//二维数组
//定义方式
/*
 *1.数据类型 数组名[行数][列数];
 *  数据类型 数组名[行数][列数]={ {数据1,数据2} , {数据3,数据4} };
 *  数据类型 数组名[行数][列数]={数据1,数据2,数据3,数据4};
 *  数据类型 数组名[][列数]={数据1,数据2,数据3,数据4};
 */
// #include<iostream>
// using namespace std;
//
// int main() {
    //1.数据类型 数组名[行数][列数];
    // int arr[2][3];
    // arr[0][0]= 1;
    // arr[0][1]= 2;
    // arr[0][2]= 3;
    // arr[1][0]= 4;
    // arr[1][1]= 5;
    // arr[1][2]= 6;
    // cout<<arr[0][0]<<endl;
    // //嵌套for循环打印，外层控制行数，内层控制列数
    // for (int i=0;i<2;i++)
    //     for (int j=0;j<3;j++)
    //         cout<<arr[i][j]<<" ";

    //2.数据类型 数组名[行数][列数]={ {数据1,数据2} , {数据3,数据4} };
    // int arr2[2][3]={
    //     {10,20,30},     //类似于生物里面的自由组合那种统计图
    //     {40,50,60}
    // };

    // 3.数据类型 数组名[行数][列数]={数据1,数据2,数据3,数据4};
    // 输入的数据自动识别先行数再列数，可读性没有第二种好
    //
    // 4.数据类型 数组名[][列数]={数据1,数据2,数据3,数据4};
    // 让计算机根据列数自己判断行数eg.[][3]三个为一行

//     return 0;
// }

//查看二维数组的内存空间、行数列数、首地址
// #include <iostream>
// using namespace std;
//
// int main() {
//     int arr3[2][3]={
//         {10,20,30},
//         {40,50,60}
//     };
//     //内存空间
//     cout<<sizeof(arr3)<<" ";
//     //行数
//     cout<<sizeof(arr3)/sizeof(arr3[0])<<endl;
//     //列数
//     cout<<sizeof(arr3[0])/sizeof(arr3[0][0])<<endl;
//     //首地址
//     //1.二维数组首地址
//     cout<<arr3<<endl;
//     //第一行首地址
//     cout<<arr3[0]<<endl;
//     //第一个元素首地址（必须取地址 即+&）
//     cout<<&arr3[0][0]<<endl;
//     return 0;
// }

//数组之打印成绩案例
// #include<iostream>
// using namespace std;
// int main(){
// //创建数组
//     string name[3]={"张三","里斯","王五"};//循环里更新名称的一种方法
//     int scores[3][3]={
//         {100,100,100},
//         {90,70,100},
//         {60,70,80}
//     };
//     for(int i=0;i<3;i++) {
//         int sum=0;
//         for(int j=0;j<3;j++) {
//             sum+=scores[i][j];//又是更新    让计算机自己记下每次循环后加上的结果
//             //cout<<scores[i][j]<<" ";
//         }
//         //cout<<"=";
//         cout<<name[i]<<"score ="<<sum;
//         // cout<<sum;
//         // cout<<endl;
//     }
//     return 0;
// }



//函数
//返回值类型 函数名（参数列表）
//{函数体语句    return 表达式}

//函数声明是什么意思？就是先告诉计算机有这个函数，然后可以在main函数之后再定义
// #include<iostream>
// using namespace std;
//
// int add(int a, int b) {
//     return a + b;
// }
// int main() {
//     int x,y;
//     x=167,y=1293;
//     cout<<add(x,y);
//     return 0;
// }

//指针
//空指针和野指针   不能随意访问
//空指针：初始化指针变量（指向的内存是不能被访问的）
// #include <iostream>
// using namespace std;
//
// int main() {
//     int *p=NULL;
//     *p = 10;//解引用
//     cout << p << endl;
//     return 0;
// }
/*常量指针-> const int * p  特点：指针的指向可以更改，也就是假设有两个地址的数值是一样的，常量指针可以来回更改两个地址，
 *但是不能更改数值
 */
//指针常量-> int * const p = &a 特点与常量指针相反
//还有一种 const int * const p 两种都不能改

//指针与数组
// #include <iostream>
// using namespace std;
//
// int main() {
//     int arr[10]={1,2,3,4,5,6,7,8,9,10};
//     int *p=arr;     //arr是数组首地址
//     cout<<*p<<endl;//相当于访问数组中第一个元素
//     // p++;            //由于声明的是整型，p++等同于向后偏移4个字节
//     // cout<<*p<<endl;
//     for (int i=0;i<10;i++) {
//         cout<<*p<<endl;
//         p++;
//     }
//     return 0;
// }


//全局变量 静态变量 常量
// #include<iostream>
// using namespace std;
//
// int main()
// {
//     int a =10;
//     cout<<"the address of 'a' is："<<&a<<endl;
//
//     return 0;
// }


//链表和list

#include <iostream>
using namespace std;

const int N = 1e6 + 5;

int e[N],ne[N],h,id;
int mp[N];//mp[i]表示i这个数存储的位置

void push_front(int x)
{
    id++;
    e[id] = x;
    mp[id] = x;
    //让新节点指向头节点原来的下一个位置
    ne[id]=ne[h];
    //再让头节点指向新来的节点
    ne[h] = id;
}

void print()
{
    for (int i = ne[h]; i ; i = ne[i]) {
        cout<<e[i]<<" ";
    }
    cout<<"\n";
}

//按值查找
int find(int x)
{
    //方法一（遍历） O(N):
    // for (int i = ne[h] ; i ;i = ne[i])
    // {
    //     if(e[i]==x) return i;
    // }
    // return 0;

    //方法二（mp优化） O(1):
    return mp[x];
}
int main() {
    for (int i = 1;i <= 5;i++) {
        push_front(i);
        print();
    }
    cout<<find(1)<<"\n";
    cout<<find(2)<<"\n";
    cout<<find(5)<<"\n";



    return 0;
}